package com.cqs.leetcode.dp;

import com.google.common.collect.Lists;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * xw
 * 2022/10/22
 */
public class EditDistance72 {


    //dp[i][j] 表示从字符串word1[0..i] 到 word2[0..j]的最少步数
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0 || word2.length() == 0) {
            return word1.length() + word2.length();
        }
        int[][] dp = new int[word1.length()][word2.length()];
        dp[0][0] = word1.charAt(0) == word2.charAt(0) ? 0 : 1;
        int idx = word2.indexOf(word1.charAt(0));
        for (int i = 0; i < word2.length(); i++) {
            dp[0][i] = idx >= 0 && i >= idx ? i : i + 1;
        }
        idx = word1.indexOf(word2.charAt(0));
        for (int i = 0; i < word1.length(); i++) {
            dp[i][0] = idx >= 0 && i >= idx ? i : i + 1;
        }

        //第一行
        for (int i = 1; i < word1.length(); i++) {
            for (int j = 1; j < word2.length(); j++) {
                int value1 = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                int value2 = dp[i - 1][j - 1] + (word1.charAt(i) == word2.charAt(j) ? 0 : 1);
                dp[i][j] = Math.min(value1, value2);
            }
        }
        return dp[word1.length() - 1][word2.length() - 1];
    }


    //回溯法 -- 超时
    //
    class Solution1 {
        Map<String, Integer> cache = new HashMap<>();

        public int minDistance(String word1, String word2) {
            cache.clear();
            return dfs(word1, 0, word1.length() - 1, word2, 0, word2.length() - 1, 0);
        }


        //怎么进行剪枝
        private int dfs(String word1, int start1, int end1, String word2, int start2, int end2, int steps) {
            String key = start1 + "-" + end1 + "-" + start2 + "-" + end2 + "-" + steps;

            if (cache.get(key) != null) {
                System.out.println("cache");
                return cache.get(key);
            }

            if (start1 > end1 || start2 > end2) {
                int result = end1 + 1 + end2 + 1 + steps - start1 - start2;
                cache.put(key, result);
                //System.out.println(key);
                return result;
            }
            //skip head
            boolean skip = false;
            while (start1 <= end1 && start2 <= end2 && word1.charAt(start1) == word2.charAt(start2)) {
                start1++;
                start2++;
                skip = true;
            }
            //skip end
            while (end1 >= start1 && end2 >= start2 && word1.charAt(end1) == word2.charAt(end2)) {
                --end1;
                --end2;
                skip = true;
            }

            if (skip) {
                return dfs(word1, start1, end1, word2, start2, end2, steps);
            }

            //添加
            int dfs = dfs(word1, start1, end1, word2, start2 + 1, end2, steps + 1);
            //删除
            int dfs1 = dfs(word1, start1 + 1, end1, word2, start2, end2, steps + 1);
            //
            int dfs2 = dfs(word1, start1 + 1, end1, word2, start2 + 1, end2, steps + 1);
            //replace
            int result = Math.min(Math.min(dfs, dfs1), dfs2);
            cache.put(key, result);
            //System.out.println(key +"----" + result);
            return result;
        }
    }


    public static void main(String[] args) {
        List<String[]> list = Lists.newArrayList();
        list.add(new String[]{"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
                , "bcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg"});
        list.add(new String[]{"teacher", "acheer"});
        list.add(new String[]{"dinitrophenylhydrazine", "benzalphenylhydrazone"});
        list.add(new String[]{"sea", "eat"});
        list.add(new String[]{"islander", "slander"});
        list.add(new String[]{"ntion", "ution"});
        list.add(new String[]{"horse", "ros"});
        list.add(new String[]{"intention", "execution"});
        list.add(new String[]{"dinitrophenylhydrazine", "acetylphenylhydrazine"});
        EditDistance72 e = new EditDistance72();
        for (String[] words : list) {
            System.out.println(Lists.newArrayList(words) + "\t" + e.minDistance(words[0], words[1]));
        }

    }
}
